import sys
from sets import Set
"""

Project Euler Problem 21 solution
Viksit Gaur 2009. 
This code is licensed under GPL.
Thanks to Greg Hewgill on Stack Overflow for a superfast divisor generator function
which now replaces my own


"""
# Calculate prime factors
def factor(n):
  yield 1
  max = n**0.5
  i = 2
  while i <= max:
    if n%i == 0:
      yield i
      n = n/i
      max = n**0.5
    else:
      i+=1
  if n>1:
    yield n

# Get factors and their multiplicity
def genfactmult(n):
  factors = list(factor(n))
  for i in factors:
    yield (i, factors.count(i))

# Uniques only
def getfactors(n):
  return list(Set(genfactmult(n)))


def getdivisors(n):
    factors = getfactors(n)
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

def getdivs(num):
  if num == 1:
    return {num : 1}
  else:
    divsa = list(Set(getdivisors(num)))
    divsa.sort()
    divsa.remove(num)
    sum = reduce(lambda x,y:x+y, divsa)
    if sum <= 10000:
      return {num : sum}
    else:
      return {}

def PE21(max):
  sd = {}
  for i in range(1,max+1):
    sd.update(getdivs(i))
  vals = {}
  for num in sd.keys():
    # If d(a) = b and d(b) = a, where a != b, then a and b 
    # are an amicable pair and each of a and b are called amicable numbers.
    if sd.has_key(sd[num]) and num == sd[sd[num]] and num!=sd[num] and (not (vals.has_key(sd[num]))):
      vals[num] = sd[num]
  print vals
  sum = reduce(lambda x,y: x+y, [i for i in vals.keys()]) + reduce(lambda x,y: x+y, [i for i in vals.values()])
  print sum

num = int(sys.argv[1])
PE21(num)
